# 定义节点
class Node():
    def __init__(self, item):
        self.elem = item   # elem是节点的元素域 , item是保存在元素域里的元素
        self.next = None   # next是节点的链接域


# 定义ADT
class SingleLinkList():

    # 初始化这个类对象，要表示是一个空链
    def __init__(self):
        self.head = None

    # 判断链表是否为空
    def is_empty(self):
        return self.head == None

    # 获取链表长度
    def length(self):
        # 创建计数器
        count = 0

        # 创建一个游标(指针cur),指向头结点
        cur = self.head

        # 移动指针,直到移动至尾节点的前一节点循环结束
        while cur != None:  
            count += 1
            cur = cur.next 
        return count

    # 遍历整个链表
    def travel(self):
        # 判断链表是否为空
        if self.is_empty():
            print('空链表')
        else:
            # 创建一个游标(指针cur),指向头结点
            cur = self.head

            # 移动指针，打印每一个节点的元素
            while cur != None:
                print(cur.elem, end=' ')
                cur = cur.next

# 在链表头部添加元素(头插法)
    def add(self, item):
        # 创建一个保存item值的节点（新节点）
        node = Node(item)

        # 将新节点的链接域next指向到头节点，即head指向的位置
        node.next = self.head

        # 将链表的头结点self.head指向新节点node
        self.head = node
   
# 在链表尾部添加元素(尾插法)
    def append(self, item):
        # 创建一个保存item值的节点（新节点）
        node = Node(item)

        # 判断链表是否为空
        '''
        若是空链表,则将head指向新节点;
        若不是空链表,则找到尾部,将尾节点的next指向新节点
        '''
        if self.is_empty():
            self.head = node
        else:
            # 创建一个游标(指针cur),指向头结点
            cur = self.head
            # 移动指针，直到找到尾节点
            while cur.next != None:
                # 指针向后移动
                cur = cur.next

            # 跳出循环，此时cur所在的位置就是链表的最后一个节点
            # 那就把 cur 的next指向到 新节点
            cur.next = node
            
# 指定位置添加元素
    '''
    pos表示指定位置的下标
    若指定位置 pos 在 第一个元素或之前-->{ pos <= 0 },则执行头部插入(头插法);
    若指定位置 pos 超过链表尾部-->{ pos > self.length() },则执行尾部插入(尾插法)
    若以上两种情况都不是,则使用游标(指针cur)寻找指定位置
    '''
    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > self.length():
            self.append(item)
        else:
            # 创建一个游标(指针cur),指向头结点
            cur = self.head

            # 创建计数器
            count = 1

            # 创建一个保存item值的新节点
            node = Node(item)

            # 移动指针,直到找到指定位置的下标
            while count < pos:
                count += 1
                cur = cur.next

            # 跳出循环之后，此时指针就在 指定位置pos 的 前一个节点
            node.next = cur.next   # 先将新节点node的链接域next指向插入位置的节点
            cur.next = node   # 再将插入位置的前一个节点的链接域next指向新节点
            '''
            注意,上面两步(node.next = cur.next  ;  cur.next = node)的顺序不可调换
            '''
            
# 删除节点
    def remove(self, item):
        # 创建游标(指针cur),指向头结点
        cur = self.head   

        # 创建游标(指针pre),指向None
        pre = None

        # 移动指针pre和cur , 直到找到指定要删除的元素
        while cur != None:
            # 如果当前的节点的 元素就是 要删除的元素
            if cur.elem == item:
                # 要删除的元素在头部
                if cur == self.head:
                    self.head = cur.next
                # 要删除的元素在链表中间或者尾部
                else:
                    pre.next = cur.next
                # 找到要删除的元素后，不要执行代码，直接return
                return

            else:
                # 如果 没有找到要删除的元素，pre和cur指针同时往后移动
                pre = cur
                cur = cur.next

# 查找节点是否存在
    def search(self, item):
        # 创建指针,指向头部
        cur = self.head

        # 移动指针
        '''
        如果指针所在节点的元素就是要查找的元素,则返回True  ;  
        否则,指针后移 , 
        直到指针指向了空节点None, 循环结束 。 此时说明在链表中并没有找到指定元素，返回False
        '''
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next

        return False
#逆顺重置链表
    def reverseOrder(self):
        t= SingleLinkList()
        cur=self.head
        while cur != None:
            t.add(cur.elem)
            cur=cur.next
        return t


'''程序入口  学过Java、C、C++的程序员应该都知道，每次开启一个程序，都必须写一个主函数作为程序的入口，
也就是我们常说的main函数。
与Java、C、C++等几种语言不同的是，Python是一种解释型脚本语言，在执行之前不同要将所有代码先编译成中间
代码，Python程序运行时是从模块顶行开始，逐行进行翻译执行，所以，最顶层（没有被缩进）的代码都会被执行，
所以Python中并不需要一个统一的main()作为程序的入口。在某种意义上讲，“if __name__==’__main__:”也像
是一个标志，象征着Java等语言中的程序主入口，告诉其他程序员，代码入口在此——这是
“if __name__==’__main__:”这条代码的意义之一。
'''
if __name__ == '__main__':

    s = SingleLinkList()  # 创建对象

    s.remove(1000)  # 链表为空时删除元素
    s.travel()
    print('-' * 40)
    
    s.append(10)   # 在链表尾部添加元素
    s.append(20)
    s.append(30)
    print("在空链表尾部依次插入三个元素10，20，30后：")
    s.travel()
    print()

    print("链表的长度=",s.length())   # 获取链表长度
    print()

    s.add(100)   # 在链表头部添加元素
    s.add(200)
    print("在链表头部添加两个元素100，200后的链表")
    s.travel()
    print()
    print("长度=",s.length())
    print()

    s.insert(2, 300)  # 在指定位置插入元素
    print("把元素300插入到第2，元素序号从零开始。0，1，2....")
    s.travel()
    print()
    print('-'*40)

    print("查找元素20是否在链表中：",s.search(20))  # 查找元素
    print("查找元素400是否在链表中：",s.search(400))
    print('-' * 40)

    s.remove(300)  # 删除中间位置元素
    print("删除元素300后的链表：")
    s.travel()
    print()
    print('-'*40)

    s.remove(200)  # 删除头部元素
    print("删除元素头部元素200后的链表：")
    s.travel()
    print()
    print('-'*40)

    s.remove(30)   # 删除尾部元素
    print("删除元素尾部元素30后的链表：")
    s.travel()
    print()
    print('-'*40)
    s.remove(400)  # 删除不存在的元素
    print("删除不存在的元素400后的链表：")
    s.travel()
    print()
    print()
    
    t=s.reverseOrder()
    print("对表进行逆序：")
    t.travel()
    print()
    print("原表：")
    s.travel()
    print()
    print()

